package com.ryujung.linked_list.leetCode_24;

/*
 * @lc app=leetcode.cn id=24 lang=java
 *
 * [24] 两两交换链表中的节点
 *
 * https://leetcode-cn.com/problems/swap-nodes-in-pairs/description/
 *
 * algorithms
 * Medium (65.26%)
 * Likes:    480
 * Dislikes: 0
 * Total Accepted:    97.3K
 * Total Submissions: 149K
 * Testcase Example:  '[1,2,3,4]'
 *
 * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 *
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 * 示例:
 *
 * 给定 1->2->3->4, 你应该返回 2->1->4->3.
 *
 */

// @lc code=start

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    ListNode(int x, ListNode next) {
        val = x;
        this.next = next;
    }
}

/**
 * 1 -> 2 -> 3 -> 4
 * 2 -> 1 -> 4 -> 3
 * 偶数项指向奇数项
 * 奇数项指向下一个奇数项
 */
class Solution {
    /**
     * 1 -> 2 -> 3 -> 4 -> 6 -> 5
     * 从尾部开始反转,递归思想
     * 2 -> 1 -> 4 -> 3 -> 6 -> 5
     **/
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode temp = head.next;

        head.next = swapPairs(temp.next);
        temp.next = head;
        return temp;
    }

    /**
     * 方式2：迭代
     * 使用三个指针，pre，用来将替换的两个节点连接到前面交换好的链表上
     * odd，even奇偶节点，每次获取奇偶节点进行交换，并将pre指向交换后的头节点
     */
    public ListNode swapPairs2(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode pre = dummy;
        ListNode odd, even;

        while (pre.next != null && pre.next.next != null) {
            odd = pre.next;
            even = pre.next.next;

            odd.next = even.next;
            even.next = odd;
            pre.next = even;
            pre = odd;
        }

        return dummy.next;
    }

    /**
     * // 2023年02月01日14:02:07追加
     * <p>
     * 题目要求不改变节点内部的值，只进行交换操作
     * 思路：
     * 跳跃遍历链表，每次将后面的两个节点进行交换操作
     * 步骤：
     * 1.创建头部pre节点，连接链表，结果返回pre.next
     * 2.判断并获取pre后面的两个节点，存在则进行交换
     */
    public ListNode swapPairs1(ListNode head) {
        ListNode pre = new ListNode(0, head);

        ListNode cur = pre;
        while (cur.next != null) {
            ListNode node1 = cur.next;
            if (node1.next == null)
                break;
            ListNode node2 = node1.next;

            //交换
            cur.next = node2;
            ListNode rest = node2.next;
            node2.next = node1;
            node1.next = rest;

            cur = node1;
        }
        return pre.next;
    }
    // 时间复杂度：O(n)
    // 空间复杂度：O(1)

}
// @lc code=end
